﻿// 1590. 使数组和能被 P 整除.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>


using namespace std;
/*
https://leetcode.cn/problems/make-sum-divisible-by-p/description/

给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。

请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。

子数组 定义为原数组中连续的一组元素。



示例 1：

输入：nums = [3,1,4,2], p = 6
输出：1
解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。
示例 2：

输入：nums = [6,3,5,2], p = 9
输出：2
解释：我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。
示例 3：

输入：nums = [1,2,3], p = 3
输出：0
解释：和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。
示例  4：

输入：nums = [1,2,3], p = 7
输出：-1
解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。
示例 5：

输入：nums = [1000000000,1000000000,1000000000], p = 3
输出：0


提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= p <= 109
*/


class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        nums.insert(nums.begin(), 0);
        vector<long long> presum(nums.size(),0);

        for (int i = 1; i < nums.size(); i++) {
            presum[i] = presum[i - 1] + nums[i];
        }

        unordered_map<int, int> mm;
        int ans = 999999999;
        for (int i = 1; i < nums.size(); i++) {
            long long rightSum = presum[nums.size() - 1] - presum[i - 1];
            long long leftSum = presum[i];
            if (leftSum % p == 0) { ans = min(ans, (int)nums.size() - i -1); }
            if (rightSum % p == 0) {
                ans = min(ans, i-1);
            }
            int find = p-rightSum % p;
            if (mm.count(find) != 0) {
                ans = min(ans,   i - mm[find] -1);
            }

            mm[presum[i-1] % p] = i-1;
        }

        if (ans == 999999999) ans = -1;

        return ans;
    }
};


int main()
{
    Solution s;
    vector<int> v{
      1000000000,1000000000,1000000000
    };
    s.minSubarray(v,3);
}

 